A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in its Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates generally to a method and apparatus for converting three dimensional data and computer models into discrete representations and displaying the resulting discrete representation on a two-dimensional display, and more particularly to a method and apparatus for real-time voxelization of three dimensional data and subsequent real-time volume rendering.
2. Related Art
Broadly speaking, three-dimensional (3D) objects tend to have different characteristics depending on their origins as either synthetic objects or empirical objects. Typical synthetic objects include computer-aided design (CAD) models, computer-aided manufacturing (CAM) models and other computer-spawned entities. Typical empirical objects include computerized tomography (CT) and magnetic resonance imaging (MRI) 3D images formed from two-dimensional (2D) xe2x80x9cslicesxe2x80x9d of empirical measurements. Typically, synthetic 3D objects are represented as 3D models. These 3D models typically reside in the memory of a computer, such as a graphics workstation or a personal computer. Typically, empirical objects are represented as volume data. These volume data typically reside in an embedded controller or computer in the device that obtained the data or in a separate computer such as a workstation or a personal computer. In many real world applications, these two types of objects need to interact (e.g., in a medical simulation where a body part is represented by empirical MRI volume data while the xe2x80x9cscalpelxe2x80x9d is a synthetic model). Typically, the results of their interaction need to be displayed on a 2D monitor. (The process of displaying a 3D object in 2D space is called rendering.)
Volume data are 3D objects from many possible sources, including synthetic objects (e.g., a CAD model) or xe2x80x9creal worldxe2x80x9d objects, such as a sequence of CT or MRI slices. In operation, data representing the volumetric objects is stored in a volume buffer of voxels (the 3D analog to pixels in 2D). Typically volume data are used to manipulate, render and display 3D objects in two related areas, volume graphics and volume visualization. Volume graphics deals with the synthesis, modeling, manipulation, rendering and display of volumetric geometric objects. Volume visualization uses interactive graphics and imaging to extract and display useful information from volumetric data.
Recent advances in volume visualization and volume-based graphics techniques have made volume graphics a potential new paradigm for the next generation computer graphics technology. One of the main obstacles for volume graphics to achieve this goal, however, is its limited support to the modeling operations of volumetric and geometric objects.
Historically, the need for direct interaction with 3D objects, such as interactive object manipulations and design, has been an important driving force for modern 3D computer graphics. A very rich set of surface graphics techniques and algorithms have been developed to provide interactive graphical display support for applications such as solid modeling and animation. In order to achieve and even surpass the capabilities of traditional surface graphics, volume graphics needs to provide efficient rendering support for applications involving dynamic volumetric scenes and interactive manipulations and operations of volumetric and geometric objects. A good background discussion of the field of volume visualization are the seminar notes found in xe2x80x9cVolume Visualization: Principles and Advancesxe2x80x9d by Dr. Arie E. Kaufman, Center for Visual Computing and Computer Science Department, State University of New York at Stony Brook, August, 1997, and incorporated herein by reference.
There are two main approaches to displaying volumetric 3D objects on a 2D display, surface rendering and volume rendering. Surface rendering uses geometric primitives to approximate a surface contained in the volumetric data. The geometric primitives can then be rendered (i.e., turned into 2D images) using conventional graphics accelerator hardware. This approach, however, has a few significant drawbacks. First, the use of geometric primitives is only an approximation, and one that may require a prohibitive number of such primitives to adequately approximate the object represented by the volumetric data. Moreover, certain objects (e.g., clouds, and fog) cannot be adequately represented using geometric primitives. Second, since the geometric primitives represent only the surface of the object, the geometric primitives do not convey any information contained within the object.
In contrast, volume rendering converts volumetric data directly into a 2D image, without the intermediate step of generating geometric primitives. This approach overcomes the disadvantages of the surface rendering approach outlined above, including preserving the volumetric data within the object. At present there are a number of volume rendering techniques that approach real time speeds through a combination of commercially available graphics Applications Programming Interface (API) software and graphics accelerator hardware.
In a volume representation, a scalar volume is a scale field sampled over a 3D regular grid in a regular volume space. A scalar value (i.e., intensity) is defined at each grid point representing a certain property (e.g., density) of the object at this point. The small cuboid formed by eight neighboring grid points is called a voxel. Thus, the intensity value of any point within a voxel can be obtained by trilinear interpolation from the eight vertices of the voxel. A binary volume is a volume having only 0 or 1 intensity values, with 1 representing a point inside an object and 0 representing a background point (i.e., a point outside the object).
The process of converting a 3D model into a volume representation is called voxelization. Conceptually voxelization (i.e., 3D scan conversion) can be considered as a set membership classification problem for all voxels in a regular volume against the given 3D model. It can also be considered as a 3D extension of the 2D scan conversion process, such as the polygon scan conversion algorithms widely used in computer graphics. Although hardware and software solutions for fast volume rendering have been developed for regular volume representations, voxelization algorithms that generate the volume representations from complex geometric and volumetric models are still too slow to support interactive modeling operations.
Several important theoretical issues have been addressed by experts in the computer graphics field. These issues include accuracy, separability (or tunnel-free) and minimality. However, the important issue of voxelization speed has heretofore received very little attention. As a result, existing voxelization algorithms, while generally adequate, are slow and not able to provide interactive feedback for object operations. In addition, existing algorithms are object-type specific. That is, a different algorithm needs to be employed for each different type of object (e.g., lines, circles, polygons, quadratic surfaces, etc.), making the implementation of a general volume graphics application difficult.
Broadly speaking, the existence of curve and surface voxelization algorithms aim to provide efficient ways to extend 2D scan conversion methods to a volumetric domain. This requires additional sampling in the third dimension for each scan line. One important difference between 2D scan conversion and voxelization is that voxelization is decoupled from the rendering process, and is therefore only done once each time the model is modified. Even so, fast voxelization is still a requirement for interactive systems where models can be modified interactively, and every model modification requires a re-voxelization.
Unlike curve/surface voxelization, the voxelization of solid objects has not been significantly studied. Early methods in solid modeling can generate the spatial enumeration representation for a solid object, which is essentially a solid voxelization process. But these are mostly brute-force algorithms and are far too slow for interactive applications. Surface voxelization methods do not generate the interior voxels that are necessary for the volumetric representation of solid objects. An algorithm disclosed by Dr. Arie Kaufman in his paper entitled, xe2x80x9cEfficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumesxe2x80x9d in SIGGRAPH ""87, volume 21, pages 171-179, July 1987, can voxelize trivariate parametric polynomial volumes. But most solid objects cannot be represented by such regular shaped trivariate parametric polynomials.
The two solid representation methods that dominate the computer graphics industry are Boundary Representation (xe2x80x9cB_Repxe2x80x9d) and Constructive Solid Geometry (xe2x80x9cCSG). A B_Rep solid object is difficult to voxelize since its interior is not explicitly defined. In fact, except for the expensive point-classification based approach proposed by Y. T. Lee and A. A. G. Requicha in their paper entitled, xe2x80x9cAlgorithms for computing the volume and other integral properties of solids,xe2x80x9d in SIGGRAPH ""94, pages 451-458, 1994, there has not been any efficient voxelization algorithm for general B_Rep solid objects.
Graphics techniques for CSG models have been studied by many researchers. The CSG representation allows users to define complex 3D solid objects by hierarchically combining simple geometric primitives using Boolean operations and affine transformations, as described by A. A. G. Requicha in xe2x80x9cRepresentation for rigid solids: Theory, methods and systems,xe2x80x9d Computing Surveys, 12(4):437-464, December 1980. CSG is a very popular and powerful solid modeling scheme, particularly for interactive object manipulations and design. Traditionally, the primitives used in a CSG construction process are defined by simple analytic objects, such as cubes, cylinders and spheres. Some recent CSG algorithms can also support primitives that are general solid models defined by their boundary surfaces.
A natural extension of the CSG method is to allow the intensity values of the volume datasets to be computed during Boolean operations. That is, objects are extracted from the volume datasets using intensity thresholding. Such models are called Volumetric-CSG models, or simply xe2x80x9cVCSGxe2x80x9d models, and are potentially useful for combining geometric and volumetric objects in one common modeling environment.
Display of CSG modeled objects cannot be accomplished directly by standard graphics workstations since such models lack explicit representation of surface boundaries. There are a number of voxelization and volume rendering techniques for CSG or VCSG models. These techniques include the Beam Oriented voxelization algorithm outlined by Naeem Shareef and Roni Yagel in an article entitled, xe2x80x9cRapid previewing via volume-based solid modeling,xe2x80x9d in Solid Modeling ""95, p 281-292, May 1995, the volume sampling approach outlined by Sidney Wang and Arie Kaufman in an article entitled, xe2x80x9cVolume-sampled 3D modeling,xe2x80x9d in IEEE computer Graphics and Application, 14:26-32, September 1994, the octree-based rendering algorithm outlined by Shiaofen Fang and R. Srinivasan in an article entitled, xe2x80x9cVolumetric CSGxe2x80x94a model-based volume visualization approach,xe2x80x9d in Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualization,xe2x80x9d pp. 88-95, February 1998, and the distance volume algorithm outlined by David E. Breen, Sean Mauch and Ross T. Whitaker in an article entitled, xe2x80x9c3D scan conversion of CSG models into distance volumes,xe2x80x9d in Proceedings of the IEEE/ACM Symposium on Volume Visualization, pp. 7-14, 1998. These algorithms typically reconstruct a volume for the entire CSG or VCSG model in some form, which is then rendered by a volume rendering algorithm. Current volume reconstruction algorithms for CSG or VCSG models are very slow, with most software implemented CSG display algorithms being too slow for interactive applications and the few interactive CSG rendering algorithms reported either require special purpose hardware or restrict the CSG model to only certain types of operations (between objects and primitives). This problem with speed becomes even more challenging with generalized CSG models, in which the operations and display of two or more different types of objects need to be combined within a common 3D environment. For these reasons, while the VCSG technique is generally adequate, it has not yet provided effective support to interactive volumetric modeling.
One approach to developing an interactive approach to displaying CSG and VCSG objects would explicitly extract the iso-surfaces from the volume data sets by using their thresholding parameters to convert the generalized CSG model into a regular geometric CSG model. At that point an existing CSG display algorithm could be used to perform rendering. This approach, however, would be relatively slow and difficult for two reasons. First, the process of iso-surface extraction is very time consuming. Second, the extracted iso-surfaces normally contain a relatively large number of polygons, which would be relatively difficult and expensive to render (as well as to operate).
Interactive object operations also require real-time rendering of volume representations. Volume rendering is a powerful technique of generating 2D images directly from volume data sets through semi-transparent rendering of both the surfaces and the internal structures of the volumetric objects. A large number of volume rendering algorithms has been developed. While these algorithms are generally adequate, they are not yet able to provide real-time volume rendering for typical-sized volumes (e.g., 2563).
Volume rendering using hardware-assisted 3D texture mapping is becoming an increasingly attractive option as 3D texture mapping hardware becomes more available, since it offers interactive rendering speed with reasonably good image quality. One example of this approach is the Volumizer application of OpenGL API by Silicon Graphics, Inc. In this approach, slices of the volume of the object parallel to the viewing plane are generated by 3D texture mapping and composited to the frame buffer in a back-to-front order to form the final image. That is, objects (such as synthetic objects) are rendered (sliced) directly to the frame buffer and that volume rendered using the depth buffer. This approach does render synthetic objects and volume objects together in a common 3D model, but the synthetic objects lack volumetric information. For instance, cutting through a solid object modeled in this fashion will result in an empty interior space.
There is therefore a need for an improved method and apparatus for voxelizing volumetric models.
The present invention relates to an apparatus and method for voxelizing geometric and volumetric models of objects in 3D space, i.e. converting these 3D models into a voxel-based volume representation. Based on an unconventional way of using the 3D graphics hardware in modern graphics workstations, the present invention generates slices of the model as frame buffer images, and then stores the slices in a 3D texture memory for interactive volume rendering. Since most of the computation is carried out directly by hardware, the voxelization algorithms of the present invention are much faster than existing algorithms, and are able to achieve interactive volume rendering and manipulation of complex 3D scenes consisting of intermixed geometric models and sampled volume data sets (e.g. CT and MRI scans). As a result, the present invention significantly enhances the capabilities of volume-based techniques (volume visualization and volume graphics) for large-scale 3D applications such as surgical planning and simulation, CAD/CAM and computer animation.
In accordance with one form of the present invention, the voxelization method of the present invention voxelizes a 3D object of predetermined 3D model type by first generating a slice of the 3D object and storing the slice in a frame buffer having blending functions. Each pixel of the frame buffer represents a voxel in the slice. In generating the slice, the method determines the type of 3D model of the object and applies predetermined frame buffer blending functions associated with that 3D model type to the voxels of each slice stored in the frame buffer. The slice is then written from the frame buffer to a plane location in a 3D memory storage matrix, with the plane location for the slice chosen to maintain the relative position of the slice to the object. The process of generating slices, storing them in the frame buffer, applying predetermined frame buffer blending functions, and storing the resulting slice in 3D memory storage matrix is repeated until the entire object has been voxelized.
In accordance with another form of the present invention, the voxelization method generates the slice directly from the surface fragments of the object within the slice without applying frame buffer blending functions, for objects determined to be curve/surface 3D model types.
In accordance with another form of the present invention, for objects determined to be boundary/surface 3D model types the voxelization method applies an XOR blending function to convey between successive slices the status of each voxel in the slice as either inside or outside of the object.
In accordance with another form of the present invention, for objects determined to be Volume Constructive Solid Geometry 3D model types, the voxelization method converts all primitives of the 3D object that are of boundary/surface 3D model type to volumes. For each binary node of the VCSG tree representing the 3D object, when creating the slices in the frame buffer, the voxelization method uses frame buffer functions to simulate the Boolean operation required at that node.
In accordance with another form of the present invention, for objects of Generalized Constructive Solid Geometry 3D model type, the voxelization method assigns each primitive composing the object a unique bit location in a color value. The frame buffer hardware pixel map is then used to classify the voxels within the slice as either inside or outside each primitive based on the color value associated with that voxel. The frame buffer hardware pixel map is used to classify the voxels within the slice as either inside or outside the object based on the classification of the voxels as either inside or outside each primitive.
In accordance with another aspect of the present invention, the method for voxelizing an object is used to voxelize a generalized CSG model of an object in 3D space by first converting the generalized CSG model into a binary volume representation of the object, then voxelizing this binary volume. The 3D space includes a plurality of coordinate points. The object is composed of a plurality of primitives. The generalized CSG model includes a generalized CSG tree having a lowest level consisting of a child node associated with each primitive of the object, at least one binary node associated with two child nodes at a level below. Each binary node includes an associated Boolean operation that governs the interaction between its associated child nodes. Each child node is associated with only a single binary node above. A leaf node is formed by the binary node at the highest level of the CSG tree and composed of two child nodes below. Each binary node other than the leaf node forms a child node for a binary node above. The step of converting to the volume model involves for each point in 3D space, creating a classification index for the point indicative of whether the point is interior to or exterior to each primitive. Next, for each primitive, a point classification map is created that maps each classification index against the primitive and its associated child node of the CSG tree. Then for each child node, a point classification map is determined for its associated binary node based on the child node""s point classification map, the point classification map of the other child node associated with its binary node, and the Boolean operation associated with the binary node. Next, for each binary node, a point classification map is determined for its associated binary node above based, on the binary node""s point classification map, the point classification map of the other node associated with the binary node above, and the Boolean operation associated with the binary node above. The point classification maps are recursively determined for binary modes until the point classification map is determined for the leaf node, thereby creating the binary volume model of the object. This binary volume model is then voxelized.
According to another aspect of the current invention, the step of creating a point classification map for each coordinate point includes the step of assigning an n-bit word to each point, where xe2x80x9cnxe2x80x9d is the number of primitives comprising the object. Each primitive is associated with a unique one of the bits of the n-bit word. The value in each bit represents whether or not the particular primitive contains the particular point to which the n-bit word is assigned.